A two-party Cramer-Shoup cryptosystem would fall into the general category of threshold cryptography. There have been previous proposals for threshold cryptosystems secure against adaptive chosen ciphertext attack.
For example, in V. Shoup et al, “Securing Threshold Cryptosystems Against Chosen Ciphertext Attack,” EUROCRYPT '98, pp. 1-16, 1998; R. Canetti et al., “An Efficient Threshold Public Key Cryptosystem Secure Against Adaptive Chosen Ciphertext Attack,” EUROCRYPT '99 (LNCS 1592), pp. 90-106, 1999; M. Abe, “Robust Distributed Multiplication without Interaction,” CRYPTO '99 (LNCS 1666), pp. 130-147, 1999; S. Jarecki et al, “Adaptively Secure Threshold Cryptography: Introducing Concurrency, Removing Erasures,” EUROCRYPT 2000 (LNCS 1807), pp. 221-242, 2000; and P. Fouque et al., “Threshold Cryptosystems Secure Against Chosen-Ciphertext Attack,” ASIACRYPT '01 (LNCS 2248), pp. 351-368, 2001, the disclosures of which are incorporated by reference herein, cryptosystems are disclosed wherein it is assumed that an adversary corrupts t out of n decryption servers.
Both the V. Shoup et al. proposal and the P. Fouque et al. proposal may be used in the two-party case (t=1, n=2) if one is only concerned with security and not robustness, but they also both use the non-standard assumption that hashes are modeled as random oracles. The random oracle assumption is discussed in M. Bellare et al., “Random Oracles are Practical: A Paradigm for Designing Efficient Protocols,” 1st ACM Conference on Computer and Communications Security, pp. 62-73, November 1993; and O. Goldreich et al., “Random Oracle Methodology, Revisited,” 30th ACM Symposium on Theory of Computing, pp. 209-218, 1998, the disclosures of which are incorporated by reference herein.
Certain of the above-mentioned proposals are based on the Cramer-Shoup cryptosystem. R. Canetti et al. assumes that there are users that wish to have messages decrypted, and that servers of the cryptosystem do not communicate with each other, but only with the users. R. Canetti et al. shows a secure system for n>2t, a secure and robust system for n>t2, and a secure and robust system for n>2t if the users are given extra per-ciphertext robustness information. In M. Abe, the servers are allowed to communicate with each other, and the disclosed techniques present secure and robust systems for n>2t. However, none of these proposals apply to the scenario where t=1 and n=2. In fact, it is often the case that threshold cryptosystems (assuming a strict minority of corrupted players) are developed before the corresponding two-party cryptosystems.
In summary, previous proposals on threshold cryptosystems secure against adaptive chosen ciphertext attack require: (1) the random oracle assumption and are thus not proven secure in a standard model; or (2) a strict majority of uncorrupted decryption servers.
Thus, there exists a need for techniques which overcome the drawbacks associated with the proposals described above and which thereby provide more efficient protocols for performing two-party Cramer-Shoup based decryption.